Many problems in Artificial Intelligence and combinatorial search applications are formulated as constraint-satisfaction problems. The solution of a constraint-satisfaction problem typically requires that an arbitrary set of constraints be satisfied. A search procedure is employed to enumerate all solutions that simultaneously satisfy all constraints on the problem. A prototypical constraint-satisfaction problem is known as the N-Queens problem and concerns the placement of N-Queens on an NxN checkerboard so that no Queen can take another.
Solution techniques that have been developed for this class of problems include the backtrack search algorithm. An example is found in a journal article entitled "Backtrack programming", Journal of the ACM, Vol. 12, 1965, pp. 516-524 by S. Golomb et al.
Variations of the backtrack search algorithm are found in the following journal articles: A. K. Mackworth, "Consistency in Networks of Relations", Artificial Intelligence, Vol. 8, pp. 99-118, 1977; R. M. Haralick and L. G. Shapiro, "The Consistent Labeling Problem: Part I", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 1, April, 1979, pp. 173-184; B. A. Nudel, "Consistent-Labeling Problems and Their Algorithms: Expected-Complexities, and Theory Based Heuristics", Artificial Intelligence (Special issue on Search and Heuristics), Vol. 21, pp. 135-178, 1983; E. C. Freuder, "A Sufficient Condition for Backtrack-Free Search", Journal of the ACM, Vol. 29, No. 1, 1982, pp. 24-32; and J. R. Bitner and E. M. Reingold, "Backtrack Programming Techniques", Comm. of the ACM, Vol. 18, pp. 651-656, 1975.
An important advantage of the backtrack search technique is that it is efficient in the use of memory space required to solve a problem. However, for many problems, a backtrack search technique can be inefficient in regards to required processing time.
One technique that is known to be efficient in the use of processing time for solving constraint-satisfaction problems is a lookahead search technique such as that known as the Forward Checker Algorithm described by R. M. Haralick and G. L. Elliott, "Improving Tree Search Efficiency for Constraint Satisfaction Problems", Artificial Intelligence pp. 263-313, 1980. However, this lookahead technique does not possess the memory usage efficiency of the backtrack search approach.
That is, at shallow levels of a search tree a lookahead search technique, such as the Forward Checker, expends a considerable amount of computation effort and time in the maintenance of memory data structures, such as keeping track of level-dependent lists of feasible values of variables. At deeper levels of the search tree, the backtrack search tends to be time inefficient for reasons described by Mackworth in the above referenced article "Consistency in Networks of Relations".
It is thus an object of the invention to provide a method for executing a search for all solutions to a constraint-satisfaction problem that includes both the memory usage efficiency of the backtrack search technique and the processing time efficiency of the lookahead search technique.